package practice;

import java.util.*;

public class Day43 {

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //统计入度并建图
        int n = prerequisites.length;
        Map<Integer,LinkedList<Integer>> map = new HashMap<>();
        int[] input = new int[numCourses];
        for(int i = 0; i < n; i++) {
            input[prerequisites[i][0]]++;
            if(map.getOrDefault(prerequisites[i][1],null) == null) {
                map.put(prerequisites[i][1],new LinkedList<>());
            }
            map.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }

        //遍历
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < numCourses; i++) {
            if(input[i] == 0) {
                stack.push(i);
            }
        }
        while(!stack.isEmpty()) {
            int top = stack.pop();
            for(int x : map.getOrDefault(top,new LinkedList<>())) {
                input[x]--;
                if(input[x] == 0) {
                    stack.push(x);
                }
            }
        }
        for(int i = 0; i < numCourses; i++) {
            if(input[i] != 0) {
                return false;
            }
        }
        return true;
    }

    private int[] dx = {0,0,1,-1};
    private int[] dy = {1,-1,0,0};
    private boolean[][] flag;
    public int numIslands(char[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        flag = new boolean[n][m];

        int ret = 0;
        Stack<int[]> stack = new Stack<>();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(grid[i][j] == '1') {
                    if(!flag[i][j]) {
                        ret++;
                    }
                    stack.push(new int[]{i,j});
                    flag[i][j] = true;
                    while(!stack.isEmpty()) {
                        int[] top = stack.pop();
                        for(int k = 0; k < 4; k++) {
                            int x = top[0] + dx[k];
                            int y = top[1] + dy[k];
                            if(x >= 0 && x < n && y >= 0 && y < m && !flag[x][y] && grid[x][y] == '1') {
                                stack.push(new int[]{x,y});
                                flag[x][y] = true;
                            }
                        }
                    }
                }
            }
        }
        return ret;
    }


    int m = 0;
    int n = 0;
    public int numIslands1(char[][] grid) {
        m = grid.length;
        n = grid[0].length;
        int count = 0;
        Queue<int[]> stack = new LinkedList<>();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == '1') {
                    stack.offer(new int[]{i,j});
                    while(!stack.isEmpty()) {
                        int[] top = stack.poll();
                        for(int k = 0; k < 4; k++) {
                            int x = dx[k] + top[0];
                            int y = dy[k] + top[1];
                            if(x >= 0 && x < m && y >= 0 && y < n && grid[i][j] == '1') {
                                grid[i][j] = '0';
                                stack.offer(new int[]{x,y});
                            }
                        }

                    }
                    count++;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Day43 day43 = new Day43();
        String[][] stringArray = {
                {"1", "1", "1", "1", "0"},
                {"1", "1", "0", "1", "0"},
                {"1", "1", "0", "0", "0"},
                {"0", "0", "0", "0", "0"}
        };
        char[][] charArray = new char[stringArray.length][stringArray[0].length];
        for (int i = 0; i < stringArray.length; i++) {
            for (int j = 0; j < stringArray[i].length; j++) {
                charArray[i][j] = stringArray[i][j].charAt(0);
            }
        }
        day43.numIslands1(charArray);
    }


    public int findMin(int[] nums) {
        int n = nums.length;
        int left = 0;
        int right = n-1;
        while(left < right) {
            int mid = (right - left) / 2 + left;
            if(nums[mid] <= nums[right]) {
                right = mid;
            }else {
                left = mid + 1;
            }
        }
        return nums[left];
    }
    public String decodeString(String s) {
        Stack<Character> stack = new Stack<>();
        StringBuilder ret = new StringBuilder();
        //从前往后放
        for(char ch : s.toCharArray()) {
            //一旦遇到]就停止，往前处理数据
            if(ch != ']') {
                stack.push(ch);
            } else {
                StringBuilder str = new StringBuilder();
                while(!stack.isEmpty() && !Character.isDigit(stack.peek())) {
                    if(Character.isLetter(stack.peek())) {
                        str.append(stack.pop());
                    }else {
                        stack.pop();
                    }
                }
                //接下来是对数字进行处理，有可能为几十，几百
                int sum = 0;
                int k = 0;
                while(!stack.isEmpty() && Character.isDigit(stack.peek())) {
                    sum += ((stack.pop()-'0') * Math.pow(10,k++));
                }
                str = str.reverse();
                while(sum != 0) {
                    for(char c : str.toString().toCharArray()) {
                        stack.push(c);
                    }
                    sum--;
                }

            }

        }
        while(!stack.isEmpty()) {
            ret.append(stack.pop());
        }
        return ret.reverse().toString();
    }
    //LRU缓存
    class Node{
        int key;
        int val;
        Node prev;
        Node next;
        public Node() {}
        public Node(int key,int value) {
            this.key = key;
            this.val = value;
        }
    }
    Map<Integer,Node> map;
    Node head;
    Node tail;
    int size;
    public LRUCache(int capacity) {
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
        n = capacity;
        map = new HashMap<>();
    }

    public int get(int key) {
        Node node = map.getOrDefault(key,null);
        if(node == null) {
            return -1;
        }else {
            moveToHead(node);
            return node.val;
        }
    }

    public void put(int key, int value) {
        Node node = map.getOrDefault(key,null);
        if(node == null) {
            //新建
            Node cur = new Node(key,value);
            map.put(key,cur);
            size++;
            addToHead(cur);
            if(size > n) {
                map.remove(tail.prev.key);
                removeNode(tail.prev);
                size--;
            }
        }else {
            moveToHead(node);
            node.val = value;
        }
    }

    private void addToHead(Node node) {
        head.next.prev = node;
        node.next = head.next;
        head.next = node;
        node.prev = head;
    }
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }
    //二叉树的直径
    int ret = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return ret;
    }
    private int depth(TreeNode root) {
        if(root == null) {
            return -1;
        }
        int leftNum = depth(root.left) + 1;
        int rightNum = depth(root.right) + 1;
        ret = Math.max(ret,rightNum+leftNum);
        return Math.max(rightNum,leftNum);
    }
    List<Integer> list = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        rightSideViewChild(root,0);
        return list;
    }
    private void rightSideViewChild(TreeNode root,int depth) {
        if(root == null) {
            return;
        }
        if(depth == list.size()) {
            list.add(root.val);
        }
        rightSideViewChild(root.right,depth+1);
        rightSideViewChild(root.left,depth+1);
    }

    Map<Long,Integer> map = new HashMap<>();
    public int pathSum(TreeNode root, int targetSum) {
        //其实就是前缀和
        map.put(0L,1);
        return dfs(root,targetSum,0L);
    }
    private int dfs(TreeNode root, int targetSum,long sum) {
        if(root == null) {
            return 0;
        }
        int ret = 0;
        sum += root.val;
        ret += map.getOrDefault(sum-targetSum,0);
        map.put(sum,map.getOrDefault(sum,0)+1);
        ret += dfs(root.left,targetSum,sum);
        ret += dfs(root.right,targetSum,sum);
        map.put(sum,map.getOrDefault(sum,0)-1);
        return ret;
    }

    public int maxProfit(int[] prices) {
        int min = 100001;
        int i = 0;
        int ret = 0;
        while(i < prices.length) {
            while(i + 1 < prices.length && prices[i] < prices[i+1]) {
                min = Math.min(prices[i],min);
                i++;
            }
            ret += Math.max(prices[i]-min,0);
            if(i+1 < prices.length) {
                min = prices[i+1];
            }
            i++;
        }
        return ret;
    }
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] f = new int[n+1];
        f[0] = 1;
        int[] g = new int[n+1];
        g[0] = 1;
        int max = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++) {
            f[i] = Math.max(nums[i-1],nums[i-1] > 0 ? nums[i-1]*f[i-1] : nums[i-1]*g[i-1]);
            g[i] = Math.min(nums[i-1],nums[i-1] < 0 ? nums[i-1]*f[i-1] : nums[i-1]*g[i-1]);
            max = Math.max(max,f[i]);
        }
        return max;
    }
    Map<Character,String> map1 = new HashMap<>();

    List<String> ret1 = new ArrayList<>();
    StringBuilder str = new StringBuilder();
    public List<String> letterCombinations(String digits) {
        map1.put('2',"abc");
        map1.put('3',"def");
        map1.put('4',"ghi");
        map1.put('5',"jkl");
        map1.put('6',"mno");
        map1.put('7',"pqrs");
        map1.put('8',"tuv");
        map1.put('9',"wxyz");
        if(digits == null || digits.length() == 0) {
            return ret1;
        }
        dfs(0,digits);
        return ret1;
    }
    private void dfs(int pos, String digits){
        if(pos == digits.length()) {
            ret1.add(new String(str));
            return;
        }
        char[] chs = map1.get(digits.charAt(pos)).toCharArray();
        for(int j = 0; j < chs.length; j++) {
            str.append(chs[j]);
            dfs(pos+1,digits);
            str.deleteCharAt(str.length()-1);
        }
    }

    public String longestPalindrome(String s) {
        int n = s.length();
        s = " " + s;
        boolean[][] dp = new boolean[n+1][n+1];
        int max = 0;
        int retI = 0;
        int retJ = 0;
        for(int j = 1; j <= n; j++) {
            for(int i = j; i > 0; i--) {
                if(s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = i+1 < j ? dp[i+1][j-1] : true;
                }
                if(dp[i][j] && max < j-i+1) {
                    max = j-i+1;
                    retI = i;
                    retJ = j;
                }
            }
        }
        return s.substring(retI,retJ+1);
    }
    private void swap(int[] nums,int a,int b){
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
    public int firstMissingPositive(int[] nums) {
        int i = 0;
        while(i < nums.length) {
            //处理两个位置相同元素，就不用交换了
            while(nums[i] > 0 && nums[i] <= nums.length && nums[nums[i]-1] != nums[i]) {
                swap(nums,nums[i]-1,i);
            }
            i++;
        }
        for(i = 0; i < nums.length; i++) {
            if(nums[i]-1 != i) {
                return i+1;
            }
        }
        return nums.length+1;
    }

}
